#include <malloc.h>
#include "util.h"
#include "mergeSort.h"


void mergeSort(int* array, int length){
    __mergeSort(array,0, length-1);
}

/**
 * 可以使用小数组进行插入排序进行优化
 * 递归使用归并排序，对array[left,right]进行排序
 * @param array
 * @param left
 * @param right
 */
static void __mergeSort(int* array, int left, int right){
    if (left >= right){
        return;
    }
    //不要使用 mid = (right + left)/2 二分查找 有可能发生溢出风险
    int mid = left + (right - left) / 2;
    __mergeSort(array,left,mid);
    __mergeSort(array,mid+1,right);
    __merge(array,left,mid,right);

}

/**
 * 将array[left,mid]和array[mid+1,right]两部分进行归并
 * @param array
 * @param left
 * @param middle
 * @param right
 */
static void __merge(int* array, int left, int middle, int right){

    //申请一个 辅助空间进行排序
    int* aux = (int*)malloc(sizeof(int)*(right-left+1));
    int i;
    for (i = left; i <= right ; i++) {
        aux[i-left] = array[i];
    }
    i = left;
    int j = middle + 1;
    int k;
    for (k = left; k <= right; k++) {
        if(i > middle){
            array[k] = aux[j-left];
            j++;
        } else if(j > right){
            array[k]  = aux[i-left];
            i++;
        } else if(aux[i-left] < aux[j-left]){
            array[k] = aux[i-left];
            i++;
        } else{
            array[k] = aux[j-left];
            j++;
        }
    }
    free(aux);
    aux = NULL;
}

void mergeSort2(int* array, int length){
    int i;
    for (i = 1; i <= length ; i += i) {
        int j;
        for (j = 0; j + i < length; j += i + i) {
            //对 array[j,j+i-1] 和 array[j+i,j+2*i-1]进行归并
            __merge(array,i,j+i-1,min(j+i+i-1,length-1));
        }
    }
}